package com.zh.note.leetcode.greedy;

import java.util.ArrayList;
import java.util.List;

/**
 * 763. 划分字母区间
 */
public class LC_763_partitionLabels {

        public List<Integer> partitionLabels(String s) {
            // 记录每个字母最远出现位置
            int[] hash = new int[27];
            for (int i = 0; i < s.length(); i++) {
                hash[s.charAt(i) - 'a'] = i;
            }
            List<Integer> res = new ArrayList<>();
            int left = 0;
            int right = 0;
            for (int i = 0; i < s.length(); i++) {
                //hash[s.charAt(i) - 'a']值表示每个字母出现的最远位置
                right = Math.max(right, hash[s.charAt(i) - 'a']);
                if (i == right) { // 找到分割线
                    //记录结果
                    res.add(right - left + 1);
                    left = i + 1;

                }
            }
            return res;
        }
}
